package java学习.代码随想录.动态规划.背包;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/23 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 零钱兑换I {
    /**
     给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
     如果没有任何一种硬币组合能组成总金额，返回 -1。
     你可以认为每种硬币的数量是无限的。
     示例 1： 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1
     示例 2： 输入：coins = [2], amount = 3 输出：-1
     示例 3： 输入：coins = [1], amount = 0 输出：0
     示例 4： 输入：coins = [1], amount = 1 输出：1
     示例 5： 输入：coins = [1], amount = 2 输出：2
     */
    /**
         * 凑成背包的最小物品数
     */
    public static int coinChange(int[] coins, int amount) {
        // int max = Integer.MAX_VALUE;
        int max = 10001;
        if (amount==0){
            return 0;
        }
        int dp [] = new int[amount+1];
        //        取最小值的话，需将数组初始化为 最大值
        for (int i = 0; i < dp.length; i++) {
            dp[i] = max;
        }
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <=amount ; j++) {
                // if(dp[j - coins[i]]!=max){

                // }
                dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
            }
        }
         System.out.println(Arrays.toString(dp));
        if (dp[amount]==max){
            return -1;
        }
        return dp[amount];
    }
    public static void main(String[] args) {
        int amount = 5;
        int[] coins = {1, 2, 5};
//        int[] coins = { 2 };
        System.out.println(coinChange(coins,amount));
        System.out.println("----------");
    }
}
